#define _CRT_SECURE_NO_WARNINGS
#include<vector>
using namespace std;
int minFallingPathSum(vector<vector<int>>& matrix) {
    int row = matrix.size();
    if (row == 1) {
        int Min = 100000;
        for (int i = 0; i < matrix[0].size(); i++) {
            if (matrix[0][i] < Min)Min = matrix[0][i];
        }
        return Min;
    }
    int col = matrix[0].size();
    vector<vector<int>> dp(row, vector<int>(col + 2));

    for (int i = 0; i < row; i++) {
        dp[i][0] = INT_MAX;
    }
    for (int i = 0; i < row; i++) {
        dp[i][col + 1] = INT_MAX;
    }
    for (int i = 1; i <= col; i++) {
        dp[0][i] = matrix[0][i - 1];
    }

    int ret = INT_MAX;
    for (int i = 1; i < row; i++) {
        for (int j = 1; j <= col; j++) {
            dp[i][j] = matrix[i][j - 1] + min(min(dp[i - 1][j - 1], dp[i - 1][j]), dp[i - 1][j + 1]);
            if (i == row - 1 && dp[i][j] < ret) ret = dp[i][j];
        }
    }
    return ret;
}
int main() {
    vector<vector<int>> arr = { {2,1,3},{6,5,4},{7,8,9} };
    int a=minFallingPathSum(arr);

    return 0;
}